#pragma once

template<class TKey, class TValue>
class TBinaryTree {
public:
    class TNode {
    public:
        typedef std::unique_ptr<TNode> TPtr;
        typedef TNode* TParentPtr;

        TNode(const TKey& key, const TValue& value)
            : Key(key)
            , Value(value)
        {
        }

        const TKey Key;
        TValue Value;

        TPtr LeftChild, RightChild;
        TParentPtr Parent;
    };

    TBinaryTree() {
    }

    TBinaryTree(TBinaryTree&& tree)
        : Root(std::move(tree.Root))
    {
    }

    explicit TBinaryTree(typename TNode::TPtr root)
        : Root(std::move(root))
    {
    }

    const TValue* Find(const TKey& key) const {
        TNode* node = Root.get();
        while (node)
            if (key < node->Key)
                node = node->LeftChild.get();
            else if (node->Key < key)
                node = node->RightChild.get();
            else
                return &node->Value;
        return nullptr;
    }

private:
    typename TNode::TPtr Root;
};
